package com.wenhao.leetcode.medium;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Wenhao Tong
 * @create 2021-07-17 20:57
 */
public class LeetCode133 {
    public static void main(String[] args) {

    }
    Map<Node,Node> map = new HashMap<>();
    public Node cloneGraph(Node node) {
        Node copy = new Node();
        copy.val = node.val;
        map.put(node,copy);
        List<Node> neighbors = new ArrayList<>();
        copy.neighbors = neighbors;
        // 为什么不会死循环？
        // 因为如果访问之前已经访问过的节点，那么一定是走if上面的分支，不会产生递归
        for (Node neighbor : node.neighbors) {
            if (map.containsKey(neighbor)) {
                neighbors.add(map.get(neighbor));
            } else {
                Node temp = cloneGraph(neighbor);
                neighbors.add(temp);
            }
        }
        return copy;
    }
}

class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
